package cn.walls1717.leetcode.array;

import cn.walls1717.leetcode.util.AlgorithmUtil;

import java.util.Arrays;

/**
 * 977. 有序数组的平方
 * 力扣地址：https://leetcode-cn.com/problems/squares-of-a-sorted-array/
 * 测试git
 *
 * @author walls1717
 * @since 2022-05-03
 **/
public class T977 {

    public static void main(String[] args) {
        int[] nums = {-4, -1, 0, 3, 10};
        System.out.println(Arrays.toString(sortedSquares2(nums)));
    }

    /**
     * 双指针法
     * 设置两个指针，一个指向数组头部，一个指向数组末尾，再设置一个新的结果数组
     * 进入循环，判断两个指针指向的元素平方大小，如果末尾指针平方大
     * 那么将末尾指针元素平方倒序放入结果数组，头部指针不动，循环末尾指针
     * 再进行判断，反之则循环头部数组
     *
     * @param nums 数组
     * @return 结果
     */
    public static int[] sortedSquares2(int[] nums) {
        // 设置新的数组，用来存放结果
        int[] result = new int[nums.length];
        // 倒序放入元素，这里要遍历数组所以设置遍历用来遍历下标
        int resultLength = result.length - 1;
        // 数组头部指针
        int i = 0;
        // 数组末尾指针
        int j = nums.length - 1;
        // 这里要 == ，因为当两个指针相等，这个元素还是要放入数组
        while (i <= j) {
            /*
             如果 j（末尾指针） 指针指向的元素平方大于 i（头部指针）指向的元素
             则将 j 指向的元素平方放入新数组的末尾
             再将 j 指针向前移，新数组下标向前移，i 指针不动
             反之 i 指针同理
             */
            if ((nums[i] * nums[i]) < (nums[j] * nums[j])) {
                result[resultLength] = nums[j] * nums[j];
                --resultLength;
                --j;
            } else {
                result[resultLength] = nums[i] * nums[i];
                --resultLength;
                ++i;
            }
        }
        return result;
    }

    /**
     * 通过排序算法实现
     * 这里试了优化过后的冒泡排序，执行时间是300多ms
     * 因此又尝试了双边快排，执行时间小了好多是6ms
     * <p>
     * 具体思想就是循环数组，对数组的每一个元素求平方
     * 求完平方之后调用排序算法进行排序
     *
     * @param nums 数组
     * @return 结果
     */
    public static int[] sortedSquares(int[] nums) {
        for (int i = 0; i < nums.length; ++i) {
            nums[i] = nums[i] * nums[i];
        }
        quick(nums, 0, nums.length - 1);
        return nums;
    }

    public static void quick(int[] nums, int l, int h) {
        if (l >= h) {
            return;
        }
        int p = partition(nums, l, h);
        quick(nums, p + 1, h);
        quick(nums, l, p - 1);
    }

    public static int partition(int[] nums, int l, int h) {
        int pv = nums[l];
        int i = l;
        int j = h;
        while (i < j) {
            while (i < j && nums[j] > pv) {
                --j;
            }
            while (i < j && nums[i] <= pv) {
                ++i;
            }
            AlgorithmUtil.swap(nums, i, j);
        }
        AlgorithmUtil.swap(nums, l, j);
        return j;
    }


}
